Skip to main content

Leetcode 746 Min Cost Climbing Stairs

· One min read

給一個整數 array, 在最多可連續跳過一個元素及頭尾可被略過的條件下，加總被選取的整數：

Problem

https://leetcode.com/problems/min-cost-climbing-stairs/

My Solution

recursion​

最先想到的是 recursion 作法

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        l = len(cost)
        if l is 1:
            return 0
        if l is 2:
            return min(cost)
        return min(cost[0]+self.minCostClimbingStairs(cost[1:]), cost[1]+self.minCostClimbingStairs(cost[2:]))

可是 TLE 了！

想想也對，因為明顯計算重疊到了

DP greedy + inplace​

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(2, len(cost)):
            cost[i] += min(cost[i-1], cost[i-2])
        return min(cost[-2:])